import java.util.Arrays;
import java.util.PriorityQueue;

public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

    public void createBigHeap() {//创造大根堆
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, usedSize);//向下调整
        }
    }

    public void siftDown(int parent, int end) {//向下调整每棵子树
        int child = parent * 2 + 1;

        while (child < end) {//每次都要调整到孩子节点的下标大于数组长度才算调完

            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {//chile+1<usedSize这是为了确保有右孩子保证child+1不会数组越界
                child++;//保证孩子节点最大值
            }
            //走完之后child是孩子最大值


            if (elem[child] > elem[parent]) {//如果孩子节点大于父亲节点就交换
                swap(child, parent);
                parent = child;//交换完之后要向下调整父亲等于孩子的下标
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    public int poll() {
        int val = elem[0];
        swap(0, usedSize - 1);//交换
        usedSize--;
        siftDown(0, usedSize);//向下调整
        return val;
    }

    //插入
    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize] = val;
        usedSize++;


        siftUp(usedSize--);
    }

    //向上调整
    public void siftUp(int child) {

        int parent = child * 2 - 1;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = child * 2 - 1;
            } else {
                break;
            }
        }


    }

    //判断数组否满员
    public boolean isFull() {
        return elem.length == usedSize;
    }


    /*
     * 堆排序*/
    public void HeapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            swap(0, end - 1);
            end--;
            siftDown(0, end);


        }

    }
    /*
    面试题 17.14. 最小K个数
    https://leetcode.cn/problems/smallest-k-lcci/
    * class Solution {

    public void creatHeap(int[] arr,int k){
        for(int parent=(k-1-1)/2;parent>=0;parent--){
            siftDonw(parent,k,arr);
        }

    }
    public void siftDonw(int parent,int end,int[] arr){//向下调整
        int child=parent*2+1;
        while(child<end){
            if(child+1<end&&arr[child]<arr[child+1]){
                child++;
            }

            if(arr[child]>arr[parent]){
                swap(child,parent,arr);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
    public void swap(int i,int j,int[] arr){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public int[] smallestK(int[] arr, int k) {
        int[] arr1=new int[k];

        creatHeap(arr,k);
        for(int i=k;i<arr.length;i++){
            if(arr[0]>arr[i]){
                swap(0,i,arr);
                siftDonw(0,k,arr);
            }
        }
        for(int j=0;j<k;j++){
            arr1[j]=arr[j];
        }
    return arr1;
    }
}
    *
    * */


}
